package algorithm.dynamic_planning.leetcode;

/**
 * @author yuisama
 * @date 2022/12/09 17:20
 * 连续子数组最大和 - 同LC 53，空间压缩
 **/
public class Offer42_MaxSubArray {
    public int maxSubArray(int[] nums) {
        // 若dp[i] 仅仅与相邻的dp[i-1]或dp[i-2]相关，可以使用临时变量暂存dp[i-1]的值，循环迭代即可
        int n = nums.length;
        int dp_0 = nums[0];
        int dp1 = 0;
        int res = dp_0;
        for (int i = 1; i < n; i++) {
            // dp[i] = Math.max(nums[i],nums[i] + dp[i - 1])
            dp1 = Math.max(nums[i],nums[i] + dp_0);
            dp_0 = dp1;
            // 顺带求最大子数组和
            res = Math.max(res,dp1);
        }
        return res;
    }
}